package likouJava;

import java.util.Arrays;

public class 最长递增子序列 {
    //动态规划
//    public int lengthOfLIS(int[] nums) {
//        int n = nums.length;;
//        int[] dp = new int[n];
//        Arrays.fill(dp,1);
//
//        int maxLen = 1;
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[j] < nums[i]){  //递增
//                    dp[i] = Math.max(dp[i], dp[j] + 1);
//                }
//            }
//            maxLen = Math.max(maxLen, dp[i]);
//        }
//        return maxLen;
//    }

    //贪心算法 + 二分查找
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;

        for (int x : nums){
            //进行二分查找
            int i = 0, j = size;
            while (i < j){
                int m = (i + j) / 2;
                if (tails[m] < x) i = m + 1;
                else j = m;
            }
            tails[i] = x;
            if (i == size) size++;
        }
        return size;
    }

}
